package com.wfm.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * 括号生成
 * 2025-02-20 17:53:55
 *
 * 为了生成所有序列，我们可以使用递归。长度为n的序列就是在长度为n−1的序列前加一个‘(’或‘)’。
 * 为了检查序列是否有效，我们遍历这个序列，并使用一个变量balance表示左括号的数量减去右括号的数量。
 * 如果在遍历过程中balance的值小于零，或者结束时balance的值不为零，那么该序列就是无效的，否则它是有效的。
 */
class GenerateParentheses {

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> combinations = new ArrayList<String>();
            generateAll(new char[2 * n], 0, combinations);
            return combinations;
        }

        public void generateAll(char[] current, int pos, List<String> result) {
            if (pos == current.length) {
                if (valid(current)) {
                    result.add(new String(current));
                }
            } else {
                current[pos] = '(';
                generateAll(current, pos + 1, result);
                current[pos] = ')';
                generateAll(current, pos + 1, result);
            }
        }

        public boolean valid(char[] current) {
            int balance = 0;
            for (char c: current) {
                if (c == '(') {
                    ++balance;
                } else {
                    --balance;
                }
                if (balance < 0) {
                    return false;
                }
            }
            return balance == 0;
        }


//    public List<String> generateParenthesis2(int n) {
//        List<String> ans = new ArrayList<String>();
//        backtrack(ans, new StringBuilder(), 0, 0, n);
//        return ans;
//    }
//
//    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
//        if (cur.length() == max * 2) {
//            ans.add(cur.toString());
//            return;
//        }
        // 优化，对于左括号小于最大个数时，可以添加左括号
//        if (open < max) {
//            cur.append('(');
//            backtrack(ans, cur, open + 1, close, max);
//            cur.deleteCharAt(cur.length() - 1);
//        }
        // 优化，对于右括号小于左括号时，可以添加右括号
//        if (close < open) {
//            cur.append(')');
//            backtrack(ans, cur, open, close + 1, max);
//            cur.deleteCharAt(cur.length() - 1);
//        }
//    }

}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        GenerateParentheses.Solution solution = new GenerateParentheses().new Solution();
    }
}